The industrialized world has been relying on fossil fuels for centuries to provide, among others, electricity, gasoline, jet fuel, plastics, and so on. As supplies of fossil fuels are limited, there is a critical need to develop alternative energy sources, including renewable energy. Microbes offer great promise to contribute a significant portion of the renewable energy.
Genome-scale flux-balance analysis (FBA) modeling has been shown to be useful for the in silico design of engineered strains of microbes that overproduce diverse targets. These engineered strains include Escherichia coli that overproduce lycopene (Alper et al. 2005 Metabolic Engineering 7(3): 155-164; and Alper et al. 2005 Nature Biotechnology 23(5): 612-616), lactic acid (Fong et al. 2005 Biotechnology and Bioengineering 91(5): 643-648), succinic acid (Lee et al. 2005 Applied and Environmental Microbiology 71(12): 7880-7887; and Wang et al. 2006 Applied Microbiology and Biotechnology 73(4): 887-894), L-valine (Park et al. 2007 Proceedings of the National Academy of Sciences, USA 104(19): 797-7802), and L-threonine (Lee et al. 2007 Molecular Systems Biology 3: 149) and strains of Saccharomyces cerevisiae that overproduce ethanol (Bro et al. 2006 Metabolic Engineering 8(2): 102-111; and Hjersted et al. 2007 Biotechnology and Bioengineering 97(5): 1190-1204). FBA models allow the result of various genetic manipulations strategies to be predicted. As a result, the space of possible genetic manipulations can be computationally searched for the strategy that results in the desired metabolic network state. This space is vast, and algorithms must be designed to search the space efficiently.
Transforming bi-level optimization of FBA models to single level mixed-integer linear programming (MILP) problems (Burgard et al. 2003 Biotechnology and Bioengineering 84(6): 647-657; Pharkya et al. 2004 Genome Research 14(11): 2367-2376; and Pharkya et al. 2006 Metabolic Engineering 8(1): 1-13) has resulted in computational methods that efficiently search the space of genetic manipulations. This approach is much more efficient than exhaustive, brute-force search, but it is nevertheless very computationally intensive. The runtimes scale exponentially as the number of manipulations allowed in the final design increases. For large models, such as the latest genome-scale model of E. coli K-12 MG1655 (Feist et al. 2007 Molecular Systems Biology 3: 121), iAF1260, it was found that this runtime generally proves prohibitive for designs involving more than a few manipulations. Given the fact that useful metabolically engineered strains often require many genetic manipulations (such as the artemisinic-acid-producing strain of S. cerevisiae by Ro et al. 2006, Nature 440(7086): 940-943), which required the addition of three genes and the up- or down-regulation of four genes) and that the number of reactions, metabolites, and genes in metabolic, models continues to grow (Feist et al. 2008 Nature Biotechnology 26(6): 659-667). There is a need for more efficient computational search techniques for effective in silico design.